The basic structure of a public key cryptosystem is well known and has become ubiquitous with security in data communication systems. Such systems use a private key k and a corresponding public key αk where α is a generator of the group. Thus one party may encrypt a message m with the intended recipients public key and the recipient may apply his private key to decrypt it.
Similarly, the cryptosystems may be used for key agreement protocols where each party exponentiates the other party's public key with their own private key. Thus party A will take B's public key αb and exponentiate it with A's private key a to obtain a session key αab. Similarly, B will take A's public key αa and exponentiate it with B's private key b to obtain the same session key αab. Thereafter data may be transferred using a symmetric key protocol utilizing the common session key.
Public key cryptosystems may also be used to sign messages to authenticate the author and/or the contents. In this case the sender will sign a message using his private key and a recipient can verify the message by applying the public key of the sender. If the received message and the recovered message correspond then the authenticity is verified.
The public key cryptosystems rely on the intractability of the discrete log problem in finite field arithmetic, that is even when the generator a and public key are known, it is computationally infeasible to obtain the corresponding private key. The security of such systems does therefore depend on the private key remaining secret. To mitigate the opportunity of disclosing the private key, protocols have been developed that use a pair of private keys and corresponding public keys, referred to as long term and short term or ephemeral key pairs respectively. The ephemeral private key is generated at the start of each session between a pair of correspondents, usually by a random number generator. The corresponding ephemeral public key is generated and the resultant key pair used in one of the possible operations described above. The long-term public key is utilized to authenticate the correspondent through an appropriate protocol. Once the session is terminated, the ephemeral key is securely discarded and a new ephemeral key generated for a new session.
Some of the more popular protocols for signature are the ElGamal family of signature schemes such as the Digital Signature Algorithm or DSA. The DSA algorithm utilizes both long term and ephemeral keys to generate a signature of the message. The DSA domain parameters are preselected. They consist of a prime number p of a predetermined length, by way of example 1024 bits; a prime number q of a predetermined bit length, by way of example 160 bits, where q divides p−1; a generator α lying between 2 and p−1 and which satisfies the condition (αa mod p)=1, and; a cryptographic hash function H, such as SHA-1.
The DSA requires the signatory to select an ephemeral key k lying between l and q−1. A first signature component r is generated from the generator a such that r=(αk mod p) mod q, A second signature component s is generated such that s=k−1(H(m)+dr)mod q, and d is the long term private key of the signatory. The signature on the message m is (r,s). The signature may be verified by computing
H(m),
u1=s−1H(m)mod q
u2=s−1r mod q
v=αu1βu2 mod p, where β=αd mod p is the long term public key of the signatory and finally verifying that r=v mod q. The use of both the ephemeral and long-term keys in the signature binds the identity of the signatory to the ephemeral key but does not render the long-term key vulnerable.
A similar signature protocol known as ECDSA may be used for elliptic curve cryptosystems. In this protocol k is selected in the interval 1 to n−1 where n is an l bit prime. The signature component r is generated by converting the x coordinate of the public key kP, where P is the seed point on the curve, to an integer mod n, i.e. r=xkp mod n. The component s=k−1(H(m)+dr)mod n and the signature on the message m is (r,s).
It will be apparent in ElGamal signature schemes such as the DSA and ECDSA, that if an ephemeral key k and the associated message m and signature (r,s) is obtained it may be used to yield the long term private key d and thereafter each of the ephemeral keys k can be obtained. Neither the DSA nor the ECDSA inherently disclose any information about the pubic key k. They both require the selection of k to be performed by a random number generator and it will therefore have a uniform distribution throughout the defined interval. However the implementation of the DSA may be done in such a way as to inadvertently introduce a bias in to the selection of k. This small bias may be exploited to extract a value of the private key d and thereafter render the security of the system vulnerable. One such implementation is the DSS mandated by the National Institute of Standards and Technology (NIST) FIPS 186-2 Standard. The DSS stipulates the manner in which an integer is to be selected for use as a private key. A seed value, SV, is generated from a random number generator which is then hashed by a SHA-1 hash function to yield a bit string of predetermined length, typically 160 bits. The bit string represents an integer between 0 and 2160−1. However this integer could be greater than the prime q and so the DSS requires the reduction of the integer mod q, i.e. k=SHA-1(seed) mod q.
Accordingly the algorithm for selecting k may be expressed as:—if SHA-1(seed)≧q then k←SHA-1(seed)−q else k←SHA-1(seed).With this algorithm it is to be expected that more values will lie in the first interval than the second and therefore there is a potential bias in the selection of k.
Recent work by Daniel Bleichenbacher suggests that the modular reduction to obtain k introduces sufficient bias in to the selection of k that an examination of 222 signatures could yield the private key d in 264 steps using 240 memory units. This suggests that there is a need for the careful selection of the ephemeral key k.